package f_graph_basics.d_find_path;

import f_graph_basics.a_graph_representation.Graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;

/**
 * 查找路径（如果有多条可能路径 - 此实现只能找到一条）
 * 从s开始寻找所有可能的路径
 * hasPath 可以判断s到另外一个顶点v之间是否存在连通的路径
 * printPath 可以打印从s到v之间的一条路径
 *
 * 当前的实现的缺点：
 * 由于每个节点只能访问一次
 * 即使存在多个路径只能能打印最先遍历到的一条
 */
public class GraphPath {
    private Graph g;
    private int s; // vertex to start
    private int[] visited; // visited[3]=1 表示索引为3的元素已经遍历过
    private int[] from; // from[3]=6表示索引为3的元素是从索引为6的元素寻路过来的

    // 深度优先遍历 - 标记从v开始的所有路径
    private void dfs(int v) {
        visited[v] = 1;
        ArrayList<Integer> edges = g.getEdgesByVertex(v);
        for (Integer edge : edges) {
            if (visited[edge] != 1) {
                from[edge] = v; // 寻路
                dfs(edge);
            }
        }
    }

    public GraphPath(Graph g, int s) {
        // 算法初始化
        assert (s >= 0 && s < g.v());
        int len = g.v();
        this.g = g;
        this.s = s;
        visited = new int[len];
        from = new int[len];
        Arrays.fill(from, -1);
        // 寻路算法
        dfs(s);
    }


    public boolean hasPath(int w) {
        assert (w >= 0 && w < g.v());
        return visited[w] == 1;
    }

    /**
     * 寻路
     * 打印s-w的所有路径
     *
     * @param w
     */
    public void printPath(int w) {
        ArrayList<Integer> vec = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        int p = w;
        while (p != -1) {
            stack.push(p);
            p = from[p];
        }
        vec.clear();
        while (!stack.isEmpty()) {
            vec.add(stack.peek());
            stack.pop();
        }
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.get(i));
            if (i == vec.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }
}
